1. Field of the Invention
This invention relates to a data processing system having virtual memory and more particularly to such a system and methods employed therein for dealing with address translation exceptions in a demand paging system.
2. Description of the Prior Art
A hierarchical memory system may be formed which memory and a low-access-speed high-capacity memory as a secondary store. The main memory is usually an integrated circuit memory and the secondary store or memory is usually a magnetic disk memory. The purpose of the main memory is to provide appropriate transfer rates to and from a processing module, with data and other information being transferred from the secondary store or memory to the main memory as required. A virtual memory system may be created by providing a hierarchical memory system with the ability to automatically transfer requested information from the secondary store to main memory when that information does not reside in main memory at the time of its request. In this manner, the user is not aware of any inherent limitations due to the size of the main memory.
The advantage of a virtual storage implementation is that not all of the stored information, either program or data, needed for the progress of the computation is required to be stored in main memory simultaneously, but that for large periods of time, parts of the stored information may reside in the secondary store. This advantage follows from the fact that main memory is generally more expensive on a per unit or per bit basis than the secondary store. For virtual memory applications, the information is partitioned lB into a number of segments such that, during the progress of the computation, the information of a segment will either be totally present in, or totally absent from, the main or primary store. If all the segments have the same size, they are generally referred to as pages, in which case the primary store is then subdivided into so-called page frames which are units of the store able to contain exactly one page.
In a virtual memory system, demand paging is provided so that computation can proceed at its full rate until an access to an absent page is required. Such a requirement is called a page fault and the computation causing the page fault is halted until the needed page can be brought into the primary store from the secondary store. As new pages are brought into the primary store, some other pages, already present in the primary store when the page fault occurred, must be sent back to the secondary store in order to make room for new pages. The number of pages or page frames provided in primary store for any given program is defined as the program window size.
Different programs, different processes within a given program, or even the same process with different data may require different program window sizes. Some processes may require a few number of instructions which are often recalled and other processes may require long strings of instructions. Some processes may require rather small amounts of data for a time while other processes may require large amounts of data at a given time.
In a computer system which implements storage address translation, the control program must be able to decide which physical page frames are allocated to pages in the large virtual address space. The most efficient means of making this decision is by demand paging. In this scheme, physical page frames are allocated to virtual pages only when required by a particular program which is executing, as indicated by an address translation exception created by that program. This requires that these exceptions be handled in the normal course of program execution, and that lB the exceptions be completely transparent to the faulting routine.
There are two basic approaches to restarting a program which has encountered an addressing exception. One is to resume the program at the instruction which created the exception. This requires that no instruction complete until the results of the storage address translation (if required) are known, and (in many cases) that a partially-executed instruction be undone so that it may be re-executed. Since the processor must wait on the results of the translation before proceeding to the next instruction, there is no overlap in this technique and performance is relatively poor. However, the reporting mechanism is simple. An indication of the type of fault and the address of the faulting instruction is all that is required by the control program The control program corrects the exception condition and restarts the faulting routine by a return-from-interrupt to the faulting instruction.
Another prior art approach to restarting a program which has encountered an addressing exception is to resume the faulting program at the point where the exception was detected. This allows the processor to overlap subsequent instruction execution with address translation, but requires that it provide enough information about the faulting operation(s) to the control program so that the operation(s) may be restarted when the faulting program is restarted. The restart procedure may be quite complex, since the control program must restart these operations under the same processor state (e.g. problem state) that existed when the original operation(s) faulted.
In order for instruction execution to be effectively overlapped with address translation, the instruction set must be defined so that storage operations are decoupled from other instructions. For example, an instruction which allows the incrementing of a given storage location must necessarily wait on the results of the address translation before it completes.
The Motorola 68010 microprocessor employs a scheme lB which restarts a faulting instruction at the point where it faulted instead of at its beginning. This eliminates the need to undo the partially executed instruction and in some cases reduces the number of virtual pages which must be allocated to storage for the faulting program when it is restarted. However, it requires that the processor save a large amount of information about its internal state (100 bytes) so that the instruction can be restarted at some intermediate point. The exception handling and restart sequence is therefore complex and inefficient. There is also little effective overlap of instruction execution with translation, but this is affected by the instruction set definition as well as the exception handling algorithm.
Another processor architecture allows the faulting routine to be restarted at the point where the exception was detected. The architecture provides a set of registers which indicate the storage operation type, address, and data. Certain instructions are defined to use the information in these registers to restart the faulting operation. This approach allows some overlap, but, since it is register-based, it limits the number of overlapped storage operations to one. Thus, sequences of multiple loads and stores, which are fairly common, do not execute at the maximum possible rate.